#include <iostream>
#include <fstream>
#include <list>
#include "graph.h"
#include "heap.h"

using namespace std;

#define INF 99999999

graph::graph(int V_num): V(V_num), adj_list(V_num) {
}

void graph::load_adj_list(const char* filename){
     int i, v1, v2, weight;
    fstream file;


    file.open(filename, fstream::in);
    if(!file){
        cerr << "No file!" << endl;
        return;
    }

    file >> V;
    file >> E;

    for(i = 0; i < E; i ++){
        file >> v1;
        file >> v2;
        file >> weight;
        adj_list[v1][v2] = weight;
        adj_list[v2][v1] = weight;
    }

	cout<<"V: "<<V<<" E: "<<E<<endl;

    return;
}

void graph::print_adj_list(){
    int i;
    map<int,int>:: iterator iter;

    for(i = 1; i <= V; i++ ){
        cout << i << ": ";
        for(iter = adj_list[i].begin(); iter != adj_list[i].end(); iter++){
            cout << iter->first << "(" << iter->second <<") ";
        }
    cout << endl;
    }
}

int graph::bellman(int V1, int V2)
{

	int infinity = 99999;

	int* D = new int[V+1];
	int* p = new int[E+1];

	map<int,int>::iterator iter;


	for(int i=0; i<V+1; i++) //INITIALIZE SINGLE SOURCE 
	{
		D[i] = infinity;
		p[i] = 0;
	}
	
	D[V1] = 0;

	/*cout<<adj_list.size();
	getchar();	

    */
	for(int j=0; j< E-2; j++)
	{
		for(int i = 1; i<adj_list.size()-1; i++)
		{
			for(iter = adj_list[i].begin(); iter != adj_list[i].end(); iter++)
			{
				if( D[i] > D[iter->first] + iter->second)
				{
					D[i] = D[iter->first] + iter->second;
					p[i] = iter->first;
				}
			}
		}
	}

	cout<<"Bellman-ford: "<<endl;

		cout<<D[V2];


	delete [] D;
	delete [] p;

	return 0;
}

int graph::prime(int beg)
{
	heap* Q = new heap();
	std::list<int> MDR;

	map<int, int>::iterator it;
	
	map<int, bool> visited;				//All nodes are not visited
	for(int i=0;i<V;i++)
	{
		visited[i] = false;
	}
	int visited_count = 0;
	int weigh_sum = 0;

	int curr = beg;
	
	while(visited_count!=V-1)
	{
	visited[curr] = true;				//Current node visited
	visited_count++;
	for(it = adj_list[curr].begin();it != adj_list[curr].end(); it++)
	{	
		if(!(visited[it->first]))
		Q->push(it->first, it->second);
	}
	
	int size = Q->size();
	curr = Q->pop_front_key();
	MDR.push_back(curr);
	}

	int s = MDR.size();
	for(int i=0;i<s;i++)
	{
		cout<<MDR.front();
		MDR.pop_front();
	}
	
	delete Q;
	return 0;
}

int graph::dijkstra(int start ,int meta){

    heap Q;
    int* droga = new int[V+1];
    int* pop= new int[V+1];
    int i,u,v;
    map<int,int>::iterator iter;

    cout << "dijkstra" << endl;

    for(i=1; i<=V; i++) // inicjalizaja
    {
        droga[i]=INF;
        Q.push(INF);
        pop[i]=0;
    }
    droga[0]=INF;
    pop[0]=0;
    droga[start]=0;
    Q.decrease_value(start,0);


    while(Q.size() != 1) // dijkstra
    {
        u=Q.pop_front_key();
        //cout << "u: " << u <<endl;

        for ( iter=adj_list[u].begin(); iter != adj_list[u].end(); iter++ ) // dla każdego sąsiada
        {
                v=iter->first; // nr wierzchołka
                if(droga[v] > droga[u] + iter->second) //(*adj[u])[v] to samo
                {
                    droga[v] = droga[u] + iter->second; //relaks
                    Q.decrease_value(v, droga[u] + iter->second);
                    pop[v]=u;
                }
        }

        //for(i=0; i<=wilosc; i++) cout << droga[i] << " ";
        //cout << endl;
    }
    //cout << *Q[0] << endl;
    //for(i=1; i<=n; i++) cout << droga[i] << endl;

    cout << "s:" << droga[meta] << endl;

	delete [] droga;
	delete [] pop;
	return 0;
}
